//332. 重新安排行程

//给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
//所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
//例如，行程["JFK", "LGA"] 与["JFK", "LGB"] 相比就更小，排序更靠前。
//假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

//class Solution {
//public:
//    vector<string> findItinerary(vector<vector<string>>& tickets) {
//        unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;
//        for (auto& it : tickets) {
//            vec[it[0]].emplace(it[1]);
//        }
//
//        vector<string> stk;
//        auto dfs = [&](this auto&& dfs, const string& curr) -> void {
//            while (vec.count(curr) && vec[curr].size() > 0) {
//                string tmp = vec[curr].top();
//                vec[curr].pop();
//                dfs(move(tmp));
//            }
//            stk.emplace_back(curr);
//        };
//
//        dfs("JFK");
//        reverse(stk.begin(), stk.end());
//        return stk;
//    }
//};

//753. 破解保险箱

//有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围[0, k - 1] 中的一个数字。
//保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。
//例如，正确的密码是 "345" ，并且你输入的是 "012345" ：
//输入 0 之后，最后 3 位输入是 "0" ，不正确。
//输入 1 之后，最后 3 位输入是 "01" ，不正确。
//输入 2 之后，最后 3 位输入是 "012" ，不正确。
//输入 3 之后，最后 3 位输入是 "123" ，不正确。
//输入 4 之后，最后 3 位输入是 "234" ，不正确。
//输入 5 之后，最后 3 位输入是 "345" ，正确，打开保险箱。
//在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。

//class Solution {
//private:
//    unordered_set<int> seen;
//    string ans;
//    int highest;
//    int k;
//
//public:
//    void dfs(int node) {
//        for (int x = 0; x < k; ++x) {
//            int nei = node * 10 + x;
//            if (!seen.count(nei)) {
//                seen.insert(nei);
//                dfs(nei % highest);
//                ans += (x + '0');
//            }
//        }
//    }
//
//    string crackSafe(int n, int k) {
//        highest = pow(10, n - 1);
//        this->k = k;
//        dfs(0);
//        ans += string(n - 1, '0');
//        return ans;
//    }
//};

//2097. 合法重新排列数对

//给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。
//如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi - 1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。
//请你返回 任意一个 pairs 的合法重新排列。
//注意：数据保证至少存在一个 pairs 的合法重新排列。

//class Solution {
//public:
//    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
//        unordered_map<int, vector<int>> g;
//        int m = pairs.size();
//        unordered_map<int, int> indeg;
//        for (const auto& p : pairs) {
//            int s = p[0], e = p[1];
//            g[s].emplace_back(e);
//            indeg[e]++;
//        }
//        vector<vector<int>> ans(m, vector<int>(2));
//        int idx = 0;
//        auto dfs = [&](auto& dfs, int x) -> void {
//            auto& nxt = g[x];
//            while (!nxt.empty()) {
//                int y = nxt.back();
//                nxt.pop_back();
//                dfs(dfs, y);
//                ans[idx][0] = x;
//                ans[idx][1] = y;
//                idx++;
//            }
//            };
//        int start = -1;
//        for (const auto& [x, out] : g) {
//            start = x;
//            if (out.size() - indeg[x] == 1) {
//                break;
//            }
//        }
//        dfs(dfs, start);
//        reverse(ans.begin(), ans.end());
//        return ans;
//    }
//};